{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Operations to Convert Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #转化数字的最小运算数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> ，该数组由 <strong>互不相同</strong> 的数字组成。另给你两个整数 <code>start</code> 和 <code>goal</code> 。</p>\n",
    "\n",
    "<p>整数 <code>x</code> 的值最开始设为 <code>start</code> ，你打算执行一些运算使 <code>x</code> 转化为 <code>goal</code> 。你可以对数字 <code>x</code> 重复执行下述运算：</p>\n",
    "\n",
    "<p>如果 <code>0 &lt;= x &lt;= 1000</code> ，那么，对于数组中的任一下标 <code>i</code>（<code>0 &lt;= i &lt; nums.length</code>），可以将 <code>x</code> 设为下述任一值：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>x + nums[i]</code></li>\n",
    "\t<li><code>x - nums[i]</code></li>\n",
    "\t<li><code>x ^ nums[i]</code>（按位异或 XOR）</li>\n",
    "</ul>\n",
    "\n",
    "<p>注意，你可以按任意顺序使用每个 <code>nums[i]</code> 任意次。使 <code>x</code> 越过 <code>0 &lt;= x &lt;= 1000</code> 范围的运算同样可以生效，但该该运算执行后将不能执行其他运算。</p>\n",
    "\n",
    "<p>返回将 <code>x = start</code><em> </em>转化为<em> </em><code>goal</code><em> </em>的最小操作数；如果无法完成转化，则返回<em> </em><code>-1</code><em> </em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,4,12], start = 2, goal = 12\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "可以按 2 → 14 → 12 的转化路径进行，只需执行下述 2 次运算：\n",
    "- 2 + 12 = 14\n",
    "- 14 - 2 = 12\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,5,7], start = 0, goal = -4\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "可以按 0 → 3 → -4 的转化路径进行，只需执行下述 2 次运算：\n",
    "- 0 + 3 = 3\n",
    "- 3 - 7 = -4\n",
    "注意，最后一步运算使 x 超过范围 0 &lt;= x &lt;= 1000 ，但该运算仍然可以生效。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,8,16], start = 0, goal = 1\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>\n",
    "无法将 0 转化为 1</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= nums[i], goal &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= start &lt;= 1000</code></li>\n",
    "\t<li><code>start != goal</code></li>\n",
    "\t<li><code>nums</code> 中的所有整数互不相同</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-operations-to-convert-number](https://leetcode.cn/problems/minimum-operations-to-convert-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-operations-to-convert-number](https://leetcode.cn/problems/minimum-operations-to-convert-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,4,12]\\n2\\n12', '[3,5,7]\\n0\\n-4', '[2,8,16]\\n0\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        vis=[0]*1001\n",
    "        vis[start]=1\n",
    "        n=len(nums)\n",
    "        q=[start]\n",
    "        step=0\n",
    "        while q :\n",
    "            tmp=q\n",
    "            q=[]\n",
    "            for x in tmp:\n",
    "                for num in nums:\n",
    "                    for nx in (x+num,x-num,x^num):\n",
    "                        if nx==goal:return step+1\n",
    "                        if 0<=nx<=1000 and vis[nx]==0:\n",
    "                            vis[nx]=1\n",
    "                            q.append(nx)\n",
    "            step+=1\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        queue = collections.deque()\n",
    "        queue.appendleft(start)\n",
    "        visited = [0] * 1001\n",
    "        visited[start] = 1\n",
    "        step = 0\n",
    "        while queue:\n",
    "            size = len(queue) # 一次性全进全出，对应同一个step\n",
    "            step += 1\n",
    "            while size > 0:\n",
    "                q = queue.pop()\n",
    "                size -= 1\n",
    "                visited[q] = 1\n",
    "                for n in nums:\n",
    "                    for q_cal in (q + n, q - n, q ^ n):\n",
    "                        if q_cal == goal:\n",
    "                            return step\n",
    "                        if q_cal >= 0 and q_cal <= 1000 and visited[q_cal] != 1:\n",
    "                            queue.appendleft(q_cal)\n",
    "                            visited[q_cal] = 1\n",
    "                \n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        vis=[0]*1001\n",
    "        vis[start]=1\n",
    "        n=len(nums)\n",
    "        q=[start]\n",
    "        step=1\n",
    "        while q :\n",
    "            tmp=q\n",
    "            q=[]\n",
    "            for x in tmp:\n",
    "                for num in nums:\n",
    "                    for nx in (x+num,x-num,x^num):\n",
    "                        if nx==goal:return step\n",
    "                        if 0<=nx<=1000 and vis[nx]==0:\n",
    "                            vis[nx]=1\n",
    "                            q.append(nx)\n",
    "            step+=1\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        q = deque([(start, 0)])\n",
    "        op1 = lambda x, y: x + y\n",
    "        op2 = lambda x, y: x - y\n",
    "        op3 = lambda x, y: x ^ y\n",
    "        ops = [op1, op2, op3]\n",
    "\n",
    "        vis = set()\n",
    "        vis.add(start)\n",
    "\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            for i in range(n):\n",
    "                for op in ops:\n",
    "                    nx = op(x, nums[i])\n",
    "                    if nx == goal:\n",
    "                        return step + 1\n",
    "                    if not nx in vis and 0 <= nx <=1000:\n",
    "                        q.append((nx, step+1))\n",
    "                        vis.add(nx)\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        visited = deque([start])\n",
    "        visited_num = [0]*1001\n",
    "        counter = 0\n",
    "        while visited:\n",
    "            counter += 1\n",
    "            for _ in range(len(visited)):\n",
    "                v = visited.popleft()\n",
    "                for num in nums:\n",
    "                    for y in [v + num, v - num, v ^ num]:\n",
    "                        if y == goal:\n",
    "                            return counter\n",
    "                        if y>1000 or y<0:\n",
    "                            continue\n",
    "                        if visited_num[y]==0:\n",
    "                            visited_num[y]=1\n",
    "                        else:\n",
    "                            continue\n",
    "                        visited.append(y)\n",
    "            # print(visited)\n",
    "        return -1\n",
    "\"\"\"class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        q = deque()\n",
    "        q.append(start)\n",
    "        visited = [False for _ in range(1001)]\n",
    "        visited[start] = True\n",
    "        step = 0\n",
    "        while q:\n",
    "            step += 1\n",
    "            for _ in range(len(q)):\n",
    "                x = q.popleft()\n",
    "                for num in nums:\n",
    "                    for y in (x + num, x - num, x ^ num):\n",
    "                        if y == goal:\n",
    "                            return step\n",
    "                        if 0 <= y <= 1000 and visited[y] == False:\n",
    "                            visited[y] = True\n",
    "                            q.append(y)\n",
    "        return -1\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "        op1 = lambda x, y: x + y\n",
    "        op2 = lambda x, y: x - y\n",
    "        op3 = lambda x, y: x ^ y\n",
    "\n",
    "        ops = [op1, op2, op3]\n",
    "\n",
    "        vis = [False] * 1001\n",
    "\n",
    "        q = deque([(start, 0)])\n",
    "\n",
    "        vis[start] = True\n",
    "\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            for i in range(n):\n",
    "                for op in ops:\n",
    "                    nx = op(x, nums[i])\n",
    "                    if nx == goal:\n",
    "                        return step + 1\n",
    "\n",
    "                    if 0 <= nx <= 1000 and not vis[nx]:\n",
    "                        vis[nx] = True\n",
    "                        q.append((nx,step + 1))\n",
    "\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        op_add = lambda x, y: x + y\n",
    "        op_sub = lambda x, y: x - y\n",
    "        op_xor = lambda x, y: x ^ y\n",
    "        ops = [op_add, op_sub, op_xor]\n",
    "        queue = deque([(start, 0)])\n",
    "        visited = [False] * 1001\n",
    "        visited[start] = True\n",
    "        while queue:\n",
    "            header = queue.popleft()\n",
    "            for num in nums:\n",
    "                for op in ops:\n",
    "                    # print(header)\n",
    "                    next_num = op(header[0], num)\n",
    "                    if next_num == goal:\n",
    "                        return header[1] + 1\n",
    "                    if 0 <= next_num <= 1000 and not visited[next_num]:\n",
    "                        queue.append((next_num,header[1]+1))\n",
    "                        visited[next_num]=True\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        op1 = lambda x, y: x + y\n",
    "        op2 = lambda x, y: x - y\n",
    "        op3 = lambda x, y: x ^ y\n",
    "        ops = [op1, op2, op3]   # 运算符列表\n",
    "        vis = [False] * 1001   # 可操作范围内整数的访问情况\n",
    "        q = deque([(start, 0)])\n",
    "        vis[start] = True\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            # 枚举数组中的元素和操作符并计算新生成的数值\n",
    "            for i in range(n):\n",
    "                for op in ops:\n",
    "                    nx = op(x, nums[i])\n",
    "                    # 如果新生成的数值等于目标值，则返回对应操作数\n",
    "                    if nx == goal:\n",
    "                        return step + 1\n",
    "                    # 如果新生成的数值位于可操作范围内且未被加入队列，则更改访问情况并加入队列\n",
    "                    if 0 <= nx <= 1000 and vis[nx] is False:\n",
    "                        vis[nx] = True\n",
    "                        q.append((nx, step + 1))\n",
    "        # 不存在从初始值到目标值的转化方案\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        op1 = lambda x, y: x + y\n",
    "        op2 = lambda x, y: x - y\n",
    "        op3 = lambda x, y: x ^ y\n",
    "        ops = [op1, op2, op3]   # 运算符列表\n",
    "        vis = [False] * 1001   # 可操作范围内整数的访问情况\n",
    "        q = deque([(start, 0)])\n",
    "        vis[start] = True\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            # 枚举数组中的元素和操作符并计算新生成的数值\n",
    "            for i in range(n):\n",
    "                for op in ops:\n",
    "                    nx = op(x, nums[i])\n",
    "                    # 如果新生成的数值等于目标值，则返回对应操作数\n",
    "                    if nx == goal:\n",
    "                        return step + 1\n",
    "                    # 如果新生成的数值位于可操作范围内且未被加入队列，则更改访问情况并加入队列\n",
    "                    if 0 <= nx <= 1000 and vis[nx] is False:\n",
    "                        vis[nx] = True\n",
    "                        q.append((nx, step + 1))\n",
    "        # 不存在从初始值到目标值的转化方案\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        op_add = lambda x, y: x + y\n",
    "        op_sub = lambda x, y: x - y\n",
    "        op_xor = lambda x, y: x ^ y\n",
    "        ops = [op_add, op_sub, op_xor]\n",
    "        queue = deque([(start, 0)])\n",
    "        visited = [False] * 1001\n",
    "        visited[start] = True\n",
    "        while queue:\n",
    "            header = queue.popleft()\n",
    "            for num in nums:\n",
    "                for op in ops:\n",
    "                    next_num = op(header[0], num)\n",
    "                    if next_num == goal:\n",
    "                        return header[1] + 1\n",
    "                    if 0 <= next_num <= 1000 and not visited[next_num]:\n",
    "                        queue.append((next_num,header[1]+1))\n",
    "                        visited[next_num]=True\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        # 定义运算\n",
    "        ld1 = lambda x, y: x + y\n",
    "        ld2 = lambda x, y: x - y\n",
    "        ld3 = lambda x, y: x ^ y\n",
    "\n",
    "        ld = [ld1, ld2, ld3]\n",
    "\n",
    "        # 防止重新计算，初始化表格记录已经被添加到队列中的数字\n",
    "        use_list = [False] * 1001\n",
    "\n",
    "        # 定义队列\n",
    "        queue = []\n",
    "        # 队列里面放什么东西呢？，数字(运算后的数字)，步数\n",
    "        queue.insert(0, (start, 0))\n",
    "\n",
    "        # 放进去之后定义start为True\n",
    "        use_list[start] = True\n",
    "\n",
    "        while queue:\n",
    "            # 获取队列data\n",
    "            data, step = queue.pop()\n",
    "\n",
    "            # 遍历nums，遍历ld进行运算\n",
    "            for i in range(len(nums)):\n",
    "                for ld_item in ld:\n",
    "                    tmp_numbers = ld_item(data, nums[i])\n",
    "                    # 判断是否满足条件\n",
    "                    if tmp_numbers == goal:\n",
    "                        return step + 1\n",
    "\n",
    "                    # 不满足条件的情况下，需要做下判断，\n",
    "                    # 不能在use_list里面使用过，数字不能超界限\n",
    "                    if 0 <= tmp_numbers <= 1000 and use_list[tmp_numbers] is False:\n",
    "                        use_list[tmp_numbers] = True\n",
    "                        queue.insert(0, (tmp_numbers, step + 1))\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        vis=[0]*1001\n",
    "        vis[start]=1\n",
    "        n=len(nums)\n",
    "        q=[start]\n",
    "        step=0\n",
    "        while q :\n",
    "            tmp=q\n",
    "            q=[]\n",
    "            for x in tmp:\n",
    "                for i in range(n):\n",
    "                    nx=x+nums[i]\n",
    "                    if nx==goal:return step+1\n",
    "                    if 0<=nx<=1000 and vis[nx]==0:\n",
    "                        vis[nx]=1\n",
    "                        q.append(nx)\n",
    "                    nx=x-nums[i]\n",
    "                    if nx==goal:return step+1\n",
    "                    if 0<=nx<=1000 and vis[nx]==0:\n",
    "                        vis[nx]=1\n",
    "                        q.append(nx)\n",
    "                    nx=x^nums[i]\n",
    "                    if nx==goal:return step+1\n",
    "                    if 0<=nx<=1000 and vis[nx]==0:\n",
    "                        vis[nx]=1\n",
    "                        q.append(nx)\n",
    "            step+=1\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], s: int, t: int) -> int:\n",
    "        q1, q2 = deque([s]), deque([t])\n",
    "        m1, m2 = {s : 0}, {t : 0}\n",
    "\n",
    "        def update(q1, m1, q2, m2, flag):\n",
    "            m = len(q1)\n",
    "            for _ in range(m):\n",
    "                x = q1.popleft()\n",
    "                step = m1[x]\n",
    "                for num in nums:\n",
    "                    # 正向搜索，出队检查\n",
    "                    if flag:\n",
    "                        if x < 0 or x > 1000:\n",
    "                            continue\n",
    "                        for nx in [x + num, x - num, x ^ num]:\n",
    "                            if nx in m2.keys():\n",
    "                                return step + 1 + m2[nx]\n",
    "                            if not nx in m1.keys():\n",
    "                                q1.append(nx)\n",
    "                                m1[nx] = step + 1\n",
    "                    else:\n",
    "                        for nx in [x + num, x - num, x ^ num]:\n",
    "                            if nx < 0 or nx > 1000:\n",
    "                                continue\n",
    "                            if nx in m2.keys():\n",
    "                                return step + 1 + m2[nx]\n",
    "                            if not nx in m1.keys():\n",
    "                                q1.append(nx)\n",
    "                                m1[nx] = step + 1\n",
    "            return -1\n",
    "\n",
    "        while q1 and q2:\n",
    "            if len(q1) <= len(q2):\n",
    "                ans = update(q1, m1, q2, m2, True)\n",
    "                if ans != -1:\n",
    "                    return ans\n",
    "            else:\n",
    "                ans = update(q2, m2, q1, m1, False)\n",
    "                if ans != -1:\n",
    "                    return ans\n",
    "        \n",
    "        return -1\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        q = deque()\n",
    "        q.append(start)\n",
    "        res = 0\n",
    "        visited = [False] * 1001\n",
    "        while len(q) != 0:\n",
    "            res += 1\n",
    "            for i in range(len(q)):\n",
    "                cur = q.popleft()\n",
    "                for incur in nums:\n",
    "                    for i in [cur + incur, cur - incur, cur ^ incur]:\n",
    "                        if i == goal:\n",
    "                            return res\n",
    "                        if 0 <= i <= 1000 and not visited[i]:\n",
    "                            visited[i] = True\n",
    "                            q.append(i)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        op1 = lambda x,y: x + y\n",
    "        op2 = lambda x,y: x - y\n",
    "        op3 = lambda x,y: x ^ y\n",
    "        op = [op1,op2,op3]\n",
    "        state = [True] * 1001\n",
    "        q = deque([(start, 1)])\n",
    "        while q:\n",
    "            preid, step = q.popleft()\n",
    "            for nu in nums:\n",
    "                for opi in op:\n",
    "                    nx = opi(preid, nu)\n",
    "                    if nx == goal:\n",
    "                        return step\n",
    "                    if 0 <= nx <= 1000 and state[nx]:\n",
    "                        q.append((nx, step+1))\n",
    "                        state[nx] = False\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        op1 = lambda x, y: x + y\n",
    "        op2 = lambda x, y: x - y\n",
    "        op3 = lambda x, y: x ^ y\n",
    "        ops = [op1, op2, op3]   # 运算符列表\n",
    "        vis = [False] * 1001   # 可操作范围内整数的访问情况\n",
    "        q = deque([(start, 0)])\n",
    "        vis[start] = True\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            # 枚举数组中的元素和操作符并计算新生成的数值\n",
    "            for i in range(n):\n",
    "                for op in ops:\n",
    "                    nx = op(x, nums[i])\n",
    "                    # 如果新生成的数值等于目标值，则返回对应操作数\n",
    "                    if nx == goal:\n",
    "                        return step + 1\n",
    "                    # 如果新生成的数值位于可操作范围内且未被加入队列，则更改访问情况并加入队列\n",
    "                    if 0 <= nx <= 1000 and vis[nx] is False:\n",
    "                        vis[nx] = True\n",
    "                        q.append((nx, step + 1))\n",
    "        # 不存在从初始值到目标值的转化方案\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, n: List[int], s: int, g: int) -> int:\n",
    "        dis = set()\n",
    "        count  = 1\n",
    "        queue = collections.deque([s])\n",
    "        dis.add(s)\n",
    "        while queue:     \n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                for i in n:\n",
    "                    for val in [node+i, node-i, node^i]:\n",
    "                        if val == g:\n",
    "                            return count\n",
    "                        else:\n",
    "                            if 0 <= val <= 1000 and val not in dis:\n",
    "                                queue.append(val)\n",
    "                                dis.add(val)\n",
    "            count += 1\n",
    "        return  -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        from collections import deque\n",
    "        \n",
    "        q = deque([(0, start)])\n",
    "        visited = {start,}\n",
    "        \n",
    "        while q:\n",
    "            step, i = q.popleft()\n",
    "            if i == goal:\n",
    "                return step \n",
    "            for j in nums:\n",
    "                for tmp in [i + j, i - j, i ^ j]:\n",
    "                    if tmp == goal:\n",
    "                        return step+1\n",
    "                    if 0 <= tmp <= 1000 and tmp not in visited:\n",
    "                        visited.add(tmp)\n",
    "                        q.append((step + 1, tmp))\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        pq = [(0, start)]\n",
    "        visited = {start}\n",
    "        while pq:\n",
    "            t, cur = heappop(pq)\n",
    "            #print(t,cur)\n",
    "            if cur == goal:\n",
    "                return t\n",
    "            #print(pq,visited)\n",
    "            for x in nums:\n",
    "                for y in (cur + x, cur - x, cur ^ x):\n",
    "                    if y not in visited:\n",
    "                        if y==goal:return t+1\n",
    "                        if 0<=y<=1000:\n",
    "                            visited.add(y)\n",
    "                            heappush(pq, (t + 1, y))\n",
    "                    \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        op1 = lambda x, y: x + y\n",
    "        op2 = lambda x, y: x - y\n",
    "        op3 = lambda x, y: x ^ y\n",
    "        ops = [op1, op2, op3]   # 运算符列表\n",
    "        vis = [False] * 1001   # 可操作范围内整数的访问情况\n",
    "        q = deque([(start, 0)])\n",
    "        vis[start] = True\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            # 枚举数组中的元素和操作符并计算新生成的数值\n",
    "            for i in range(n):\n",
    "                for op in ops:\n",
    "                    nx = op(x, nums[i])\n",
    "                    # 如果新生成的数值等于目标值，则返回对应操作数\n",
    "                    if nx == goal:\n",
    "                        return step + 1\n",
    "                    # 如果新生成的数值位于可操作范围内且未被加入队列，则更改访问情况并加入队列\n",
    "                    if 0 <= nx <= 1000 and vis[nx] is False:\n",
    "                        vis[nx] = True\n",
    "                        q.append((nx, step + 1))\n",
    "        # 不存在从初始值到目标值的转化方案\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        from collections import deque\n",
    "        \n",
    "        q = deque([(0,start)])\n",
    "        visited = {start,}\n",
    "        \n",
    "        while q:\n",
    "            step,i = q.popleft()\n",
    "            if i==goal:\n",
    "                return step \n",
    "            for j in nums:\n",
    "                for tmp in [i+j,i-j,i^j]:\n",
    "                    if tmp==goal:\n",
    "                        return step+1\n",
    "                    if 0<=tmp<=1000 and tmp not in visited:\n",
    "                        visited.add(tmp)\n",
    "                        q.append((step+1,tmp))\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        # BFS扩散\n",
    "        q = deque([(start,0)])\n",
    "        vis = [False]*(1001)\n",
    "        while q:\n",
    "            x,time = q.popleft()\n",
    "            for y in nums:\n",
    "                if x+y == goal:\n",
    "                    return time + 1\n",
    "                if 0 <= x+y <= 1000 and vis[x+y] == False:\n",
    "                    vis[x+y] = True\n",
    "                    q.append((x+y,time+1))\n",
    "                if x-y == goal:\n",
    "                    return time + 1  \n",
    "                if 0 <= x-y <= 1000 and vis[x-y] == False:\n",
    "                    vis[x-y] = True\n",
    "                    q.append((x-y,time+1))\n",
    "                if x^y == goal:\n",
    "                    return time + 1\n",
    "                if 0 <= x^y <= 1000 and vis[x^y] == False:\n",
    "                    vis[x^y] = True\n",
    "                    q.append((x^y,time+1))\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums, start: int, goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        vst = [0] * 1001\n",
    "        vst[start] = 1\n",
    "        q = deque([(start, 0)])\n",
    "        ops = [lambda x, y: x + y, lambda x, y: x - y, lambda x, y: x ^ y]\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            for i in range(n):\n",
    "                for op in ops:\n",
    "                    y = op(x, nums[i])\n",
    "                    if y == goal:\n",
    "                        return step + 1\n",
    "                    if 0 <= y <= 1000 and not vst[y]:\n",
    "                        vst[y] = 1\n",
    "                        q.append((y, step + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        # BFS扩散\n",
    "        q = [(start,0)]\n",
    "        vis = [False]*(1001)\n",
    "        while q:\n",
    "            x,time = q.pop(0)\n",
    "            for y in nums:\n",
    "                if x+y == goal:\n",
    "                    return time + 1\n",
    "                if 0 <= x+y <= 1000 and vis[x+y] == False:\n",
    "                    vis[x+y] = True\n",
    "                    q.append((x+y,time+1))\n",
    "                if x-y == goal:\n",
    "                    return time + 1  \n",
    "                if 0 <= x-y <= 1000 and vis[x-y] == False:\n",
    "                    vis[x-y] = True\n",
    "                    q.append((x-y,time+1))\n",
    "                if x^y == goal:\n",
    "                    return time + 1\n",
    "                if 0 <= x^y <= 1000 and vis[x^y] == False:\n",
    "                    vis[x^y] = True\n",
    "                    q.append((x^y,time+1))\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        op1 = lambda x, y: x + y\n",
    "        op2 = lambda x, y: x - y\n",
    "        op3 = lambda x, y: x ^ y\n",
    "        ops = [op1, op2, op3]   # 运算符列表\n",
    "        vis = [False] * 1001   # 可操作范围内整数的访问情况\n",
    "        q = deque([(start, 0)])\n",
    "        vis[start] = True\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            # 枚举数组中的元素和操作符并计算新生成的数值\n",
    "            for i in range(n):\n",
    "                for op in ops:\n",
    "                    nx = op(x, nums[i])\n",
    "                    # 如果新生成的数值等于目标值，则返回对应操作数\n",
    "                    if nx == goal:\n",
    "                        return step + 1\n",
    "                    # 如果新生成的数值位于可操作范围内且未被加入队列，则更改访问情况并加入队列\n",
    "                    if 0 <= nx <= 1000 and vis[nx] is False:\n",
    "                        vis[nx] = True\n",
    "                        q.append((nx, step + 1))\n",
    "        # 不存在从初始值到目标值的转化方案\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        q = {start,}\n",
    "        r = {start,}\n",
    "        ans = 0\n",
    "        x = start\n",
    "        \n",
    "        while q :\n",
    "            r2 = set()\n",
    "            for x in q :\n",
    "                for i in nums :\n",
    "                    t1,t2,t3 = x+i,x- i,x^i\n",
    "                    if t1 == goal :\n",
    "                        return ans + 1\n",
    "                    elif t1 not in r and 0<=t1<=1000:\n",
    "                        r.add(t1)\n",
    "                        r2.add(t1)\n",
    "                    t1 = x -i\n",
    "                    if t1 == goal :\n",
    "                        return ans + 1\n",
    "                    elif t1 not in r and 0<=t1<=1000:\n",
    "                        r.add(t1)\n",
    "                        r2.add(t1)\n",
    "                    t1 = x^i\n",
    "                    if t1 == goal :\n",
    "                        return ans + 1\n",
    "                    elif t1 not in r and 0<=t1<=1000:\n",
    "                        r.add(t1)\n",
    "                        r2.add(t1)\n",
    "            ans +=1            \n",
    "            q=r2.copy()\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        numDict = collections.defaultdict(int)\n",
    "        queue = collections.deque([start])\n",
    "        visited = {start: 0}\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for i in nums:\n",
    "                if goal in (cur + i, cur - i, cur ^ i):\n",
    "                    return visited[cur] + 1\n",
    "                if cur + i not in visited and 0 <= cur + i <= 1000:\n",
    "                    visited[cur + i] = visited[cur] + 1\n",
    "                    queue.append(cur + i)\n",
    "                if cur - i not in visited and 0 <= cur - i <= 1000:\n",
    "                    visited[cur - i] = visited[cur] + 1\n",
    "                    queue.append(cur - i)\n",
    "                if cur ^ i not in visited and 0 <= cur ^ i <= 1000:\n",
    "                    visited[cur ^ i] = visited[cur] + 1\n",
    "                    queue.append(cur ^ i) \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        op1 = lambda x, y: x + y\n",
    "        op2 = lambda x, y: x - y\n",
    "        op3 = lambda x, y: x ^ y\n",
    "        op = [op1, op2, op3]\n",
    "\n",
    "        state = [False] * 1001\n",
    "        state[start] = True\n",
    "        q = deque([(start, 1)])\n",
    "        while q:\n",
    "            weizhi, step = q.popleft()\n",
    "            for nu in nums:\n",
    "                for i in range(3):\n",
    "                    nx = op[i](weizhi, nu)\n",
    "                    if nx == goal:\n",
    "                        return step\n",
    "                    elif 0<= nx <= 1000 and not state[nx]:\n",
    "                        state[nx] = True\n",
    "                        q.append((nx, step+1))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        from collections import deque\n",
    "        \n",
    "        q = deque([(0, start)])\n",
    "        visited = {start, }\n",
    "        \n",
    "        while q:\n",
    "            step, i = q.popleft()\n",
    "            if i == goal:\n",
    "                return step \n",
    "            for j in nums:\n",
    "                for tmp in [i + j, i - j, i ^ j]:\n",
    "                    if tmp == goal:\n",
    "                        return step + 1\n",
    "                    if 0 <= tmp <= 1000 and tmp not in visited:\n",
    "                        visited.add(tmp)\n",
    "                        q.append((step + 1, tmp))\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        qu = []\n",
    "        qu.append((start, 0))\n",
    "        vi = [0] * 1001\n",
    "        def bfs():\n",
    "            print(qu)\n",
    "            while len(qu) > 0:\n",
    "                temp = qu.pop(0)\n",
    "                for i in range(len(nums)):\n",
    "                    tempi = temp[0] + nums[i]\n",
    "                    if tempi == goal:\n",
    "                        return temp[1] + 1\n",
    "                    if tempi <= 1000 and tempi >= 0 and vi[tempi] == 0:\n",
    "                        qu.append((tempi, temp[1] + 1))\n",
    "                        vi[tempi] =1\n",
    "                    tempi = temp[0] - nums[i]\n",
    "                    if tempi == goal:\n",
    "                        return temp[1] + 1\n",
    "                    if tempi <= 1000 and tempi >= 0 and vi[tempi] == 0:\n",
    "                        qu.append((tempi, temp[1] + 1))\n",
    "                        vi[tempi] =1\n",
    "                    tempi = temp[0] ^ nums[i]\n",
    "                    if tempi == goal:\n",
    "                        return temp[1] + 1\n",
    "                    if tempi <= 1000 and tempi >= 0 and vi[tempi] == 0:\n",
    "                        qu.append((tempi, temp[1] + 1))\n",
    "                        vi[tempi] =1\n",
    "            return -1\n",
    "        out = bfs()\n",
    "        return out\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        q1, q2 = deque([start]), deque([goal])\n",
    "        m1 = {start : 0}\n",
    "        m2 = {goal : 0}\n",
    "\n",
    "        def update(q1, m1, q2, m2, flag):\n",
    "            for _ in range(len(q1)):\n",
    "                x = q1.popleft()\n",
    "                step = m1[x]\n",
    "                for num in nums:\n",
    "                    # 正向\n",
    "                    if flag:\n",
    "                        if x < 0 or x > 1000:\n",
    "                            continue\n",
    "                        for nx in [x + num, x - num, x ^ num]:\n",
    "                            if nx in m2:\n",
    "                                return step + 1 + m2[nx]\n",
    "                            if not nx in m1:\n",
    "                                q1.append(nx)\n",
    "                                m1[nx] = step + 1\n",
    "                    # 反向看输入\n",
    "                    else:\n",
    "                        for nx in [x + num, x - num, x ^ num]:\n",
    "                            if nx < 0 or nx > 1000:\n",
    "                                continue\n",
    "                            if nx in m2:\n",
    "                                return step + 1 + m2[nx]\n",
    "                            if not nx in m1:\n",
    "                                q1.append(nx)\n",
    "                                m1[nx] = step + 1\n",
    "            return -1\n",
    "        \n",
    "        \n",
    "        while q1 and q2:\n",
    "            if len(q1) <= len(q2):\n",
    "                ans = update(q1, m1, q2, m2, True)\n",
    "                if ans != -1:\n",
    "                    return ans\n",
    "            else:\n",
    "                ans = update(q2, m2, q1, m1, False)\n",
    "                if ans != -1:\n",
    "                    return ans\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        from collections import deque\n",
    "        \n",
    "        q = deque([(0,start)])\n",
    "        visited = {start,}\n",
    "        \n",
    "        while q:\n",
    "            step,i = q.popleft()\n",
    "            if i==goal:\n",
    "                return step \n",
    "            for j in nums:\n",
    "                for tmp in [i+j,i-j,i^j]:\n",
    "                    if tmp==goal:\n",
    "                        return step+1\n",
    "                    if 0<=tmp<=1000 and tmp not in visited:\n",
    "                        visited.add(tmp)\n",
    "                        q.append((step+1,tmp))\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "\n",
    "# 创建一个队列\n",
    "queue = Queue()\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        op1 = lambda x, y: x + y\n",
    "        op2 = lambda x, y: x - y\n",
    "        op3 = lambda x, y: x ^ y\n",
    "        ops = [op1, op2, op3]   # 运算符列表\n",
    "        vis = [False] * 1001   # 可操作范围内整数的访问情况\n",
    "        q = deque([(start, 0)])\n",
    "        vis[start] = True\n",
    "        while q:\n",
    "            x, step = q.popleft()\n",
    "            # 枚举数组中的元素和操作符并计算新生成的数值\n",
    "            for i in range(n):\n",
    "                for op in ops:\n",
    "                    nx = op(x, nums[i])\n",
    "                    # 如果新生成的数值等于目标值，则返回对应操作数\n",
    "                    if nx == goal:\n",
    "                        return step + 1\n",
    "                    # 如果新生成的数值位于可操作范围内且未被加入队列，则更改访问情况并加入队列\n",
    "                    if 0 <= nx <= 1000 and vis[nx] is False:\n",
    "                        vis[nx] = True\n",
    "                        q.append((nx, step + 1))\n",
    "        # 不存在从初始值到目标值的转化方案\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        a = set()\n",
    "\n",
    "        def bfs(x, ans):\n",
    "            if len(x) == 0:\n",
    "                return -1\n",
    "            ans += 1\n",
    "            tmp = set()\n",
    "            for i in x:\n",
    "                for num in nums:\n",
    "                    if i + num == goal:\n",
    "                        return ans\n",
    "                    elif 0 <= i + num <= 1000 and (i + num) not in a:\n",
    "                        tmp.add(i + num)\n",
    "                        a.add(i + num)\n",
    "                    if i - num == goal:\n",
    "                        return ans\n",
    "                    elif 0 <= i - num <= 1000 and (i - num) not in a:\n",
    "                        tmp.add(i - num)\n",
    "                        a.add(i - num)\n",
    "                    if i ^ num == goal:\n",
    "                        return ans\n",
    "                    elif 0 <= i ^ num <= 1000 and (i ^ num) not in a:\n",
    "                        tmp.add(i ^ num)\n",
    "                        a.add(i ^ num)\n",
    "            return bfs(tmp, ans)\n",
    "\n",
    "        return bfs({start}, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        if start == goal: return 0\n",
    "        visited = set()\n",
    "        queue = deque([start])\n",
    "        res = 0\n",
    "        while len(queue) != 0:\n",
    "            for _ in range(len(queue)):\n",
    "                cn = queue.popleft()\n",
    "                if cn == goal: return res\n",
    "                if cn < 0 or cn > 1000 or cn in visited: continue\n",
    "                visited.add(cn)\n",
    "                for i in nums:\n",
    "                    queue.append(cn + i)\n",
    "                    queue.append(cn - i)\n",
    "                    queue.append(cn ^ i)\n",
    "            res += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        # BFS扩散\n",
    "        q = [start]\n",
    "        vis = [False]*(1001)\n",
    "        time = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                if x == goal:\n",
    "                    return time\n",
    "                if x < 0 or x > 1000:\n",
    "                    continue\n",
    "                if vis[x]:\n",
    "                    continue\n",
    "                vis[x] = True \n",
    "                for y in nums:\n",
    "                    q.append(x+y)\n",
    "                    q.append(x-y)\n",
    "                    q.append(x^y)\n",
    "            time += 1\n",
    "        return -1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        # BFS扩散\n",
    "        q = [start]\n",
    "        seen = set()\n",
    "        time = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                if x == goal:\n",
    "                    return time\n",
    "                if x < 0 or x > 1000 or x in seen:\n",
    "                    continue\n",
    "                seen.add(x)\n",
    "                for y in nums:\n",
    "                    q.append(x+y)\n",
    "                    q.append(x-y)\n",
    "                    q.append(x^y)\n",
    "            time += 1\n",
    "        return -1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        # 目标 start -> goal\n",
    "        # 如果start一直在0 <=start <= 1000范围内那么可以进行任意次操作\n",
    "        q = [start]\n",
    "        seen = set()\n",
    "        time = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                if x == goal:\n",
    "                    return time\n",
    "                if x < 0 or x > 1000 or x in seen:\n",
    "                    continue\n",
    "                seen.add(x)\n",
    "                for y in nums:\n",
    "                    q.append(x + y)\n",
    "                    q.append(x - y)\n",
    "                    q.append(x ^ y)\n",
    "            time += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        visit = {start}\n",
    "        \n",
    "        stack = deque([[start, 0]])\n",
    "        while stack:\n",
    "            x, d = stack.popleft()\n",
    "            if x == goal:\n",
    "                return d\n",
    "            if not 0<=x<=1000:\n",
    "                continue\n",
    "            for num in nums:\n",
    "                if x+num not in visit:\n",
    "                    visit.add(x+num)\n",
    "                    stack.append([x+num, d+1])\n",
    "                \n",
    "                if x-num not in visit:\n",
    "                    visit.add(x-num)\n",
    "                    stack.append([x-num, d+1])\n",
    "\n",
    "                if x ^ num not in visit:\n",
    "                    visit.add(x ^ num)\n",
    "                    stack.append([x ^ num, d + 1])\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\r\n",
    "        s = set()\r\n",
    "        q = [start]\r\n",
    "        res = 0 \r\n",
    "        while q:\r\n",
    "            tmp = q\r\n",
    "            q = []\r\n",
    "            for x in tmp:\r\n",
    "                if x == goal:\r\n",
    "                    return res \r\n",
    "                if 0 <= x <= 1000:\r\n",
    "                    for y in nums:\r\n",
    "                        if x + y not in s:\r\n",
    "                            s.add(x + y)\r\n",
    "                            q.append(x + y)\r\n",
    "                        if x - y not in s:\r\n",
    "                            s.add(x - y)\r\n",
    "                            q.append(x - y) \r\n",
    "                        if x ^ y not in s:\r\n",
    "                            s.add(x ^ y)\r\n",
    "                            q.append(x ^ y)\r\n",
    "            res += 1\r\n",
    "        return -1\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        n=len(nums)\n",
    "        visited=set()\n",
    "\n",
    "        step=-1\n",
    "        q=[start]\n",
    "        visited.add(start)\n",
    "\n",
    "        while q:\n",
    "            step+=1\n",
    "            t=len(q)\n",
    "            for i in range(t):\n",
    "                temp=q[i]\n",
    "                if temp==goal:return step\n",
    "                if temp>1000 or temp<0:continue\n",
    "                for j in nums:\n",
    "                    if temp+j not in visited:\n",
    "                        visited.add(temp+j)\n",
    "                        q.append(temp+j)\n",
    "                    \n",
    "                    if temp-j not in visited:\n",
    "                        visited.add(temp-j)\n",
    "                        q.append(temp-j)\n",
    "\n",
    "                    if temp^j not in visited:\n",
    "                        visited.add(temp^j)\n",
    "                        q.append(temp^j)\n",
    "            q=q[t:]\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        vis = set()\n",
    "        q = deque()\n",
    "        vis.add(start)\n",
    "        q.append([start,0])\n",
    "        while q:\n",
    "            cur,d = q.popleft()\n",
    "            if cur == goal:\n",
    "                return d\n",
    "            if cur > 1000 or cur < 0:\n",
    "                continue\n",
    "            for c in nums:\n",
    "                if cur + c not in vis:\n",
    "                    vis.add(cur + c)\n",
    "                    q.append([cur + c,d + 1])\n",
    "                if cur - c not in vis:\n",
    "                    vis.add(cur - c)\n",
    "                    q.append([cur - c,d + 1])\n",
    "                if cur ^ c not in vis:\n",
    "                    vis.add(cur ^ c)\n",
    "                    q.append([cur ^ c,d + 1])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:\n",
    "        if start == goal :\n",
    "            return 0\n",
    "\n",
    "        q = deque([start])\n",
    "        visit = set()\n",
    "        level = 0\n",
    "\n",
    "        while q :\n",
    "            tmp = deque([])\n",
    "            for _ in range(len(q)) :\n",
    "                node = q.popleft()\n",
    "                if node > 1000 or node < 0:\n",
    "                    continue\n",
    "\n",
    "                for num in nums :\n",
    "                    for net in [node + num, node - num, node ^ num] :\n",
    "                        if net == goal :\n",
    "                            return level+1\n",
    "                        if net not in visit :\n",
    "                            visit.add(net)\n",
    "                            tmp.append(net)\n",
    "            q = tmp \n",
    "            level += 1\n",
    "\n",
    "        return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
